package ext;

import java.util.*;

import org.junit.Test;


public class Backpack1 {
    public int maxValue(int W, int[] w, int[] v) {
        int m = w.length;
        int[] f = new int[W + 1];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = W; j >= w[i]; j--) {
                f[j] = Math.max(f[j],f[j - w[i]] + v[i]);
            }
        }
        return f[W];
    }

    public int infinityMaxValue(int W, int[] w, int[] v) {
        int n = w.length;
        int[] f = new int[W + 1];
        //f[n] = 0; //没有物品，没有价值
        for (int i = n - 1; i >= 0; i--) {
            // for (int j = W; j >= 0; j--) {
            for (int j = w[i]; j <= W; j++) {
                //依赖的是上一轮的，而不是这一轮的，需要获取上一轮没有更新的，因此从高向低遍历
                f[j] = Math.max(f[j], f[j - w[i] + v[i]]);
            }
        }
        return f[W];
    }

    @Test
    public void test() {
        int[] v = {4,2,3}, w = {4,2,3};
        System.out.println(maxValue(5, w, v));
    }


    public int coins(int[] coins, int v) {
        int[] f = new int[v + 1];
        int m = coins.length;
        Arrays.fill(f, Integer.MAX_VALUE);
        f[0] = 0;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = coins[i]; j <= v; j++) {
                if (f[i - coins[i]] != Integer.MAX_VALUE)
                    f[j] = Math.min(f[j], f[j - coins[i]] + 1);
            }
        }
        return f[v];
    }

    public int multipleMaxValue1(int N, int C, int[] s, int[] v, int[] w) {

        int[][] f = new int[N + 1][C + 1];
        //f全为0
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 0; j <= C; j++) {
                for (int k = 1; k <= s[i]; k++) {
                    int t = j - k * w[i];
                    if (t >= 0) {
                        f[i][j] = Math.max(f[i][j], f[i + 1][t] + k * v[i]);
                    } else {
                        break;
                    }
                }
            }
        }
        System.out.println(Arrays.deepToString(f));


        return f[0][C];
    }

    public int multipleMaxValue(int N, int C, int[] s, int[] v, int[] w) {

        int[] f = new int[C + 1];
        //f全为0
        for (int i = N - 1; i >= 0; i--) {
            for (int j = C; j >= w[i]; j--) {
                for (int k = 1; k <= s[i]; k++) {
                    int t = j - k * w[i];
                    if (t >= 0) {
                        f[j] = Math.max(f[j], f[t] + k * v[i]);
                    } else {
                        break;
                    }
                }
            }
            System.out.println(Arrays.toString(f));
        }

        return f[C];
    }

    @Test
    public void test4() {
        int[] nums = new int[]{1,2}, s = {2,1};
        System.out.println(multipleMaxValue1(2,5, s, nums, nums));
        System.out.println(multipleMaxValue(2,5, s, nums, nums));
    }

    //s: s[i] == 0, 只能取一次；s[i] < 0, 取无限次； s[i] > 0, 最多取s[i]次
    public int mixedMaxValue(int N, int C, int[] s, int[] v, int[] w) {
        int[] f = new int[C + 1];
        for (int i = N - 1; i >= 0; i--) {
            for (int j = C; j >= w[i]; j--) {
                int t = s[i], cur;
                switch (t) {
                    case 0: 
                        cur = j - w[i];
                        f[j] = Math.max(f[j], f[cur] + v[i]);
                        break;
                    case -1:
                        for (int k = 1; (cur = j - k * w[i]) >= 0; k++) {
                            f[j] = Math.max(f[j], f[cur] + k * v[i]);
                        }
                        break;
                    default:
                        for (int k = 1; k <= t && (cur = j - k * w[i]) >= 0; k++) {
                            f[j] = Math.max(f[j], f[cur] + k * v[i]);
                        }
                }
            }
        }


        return f[C];
    }


    //使用二进制优化来解决背包问题
    class Solution  {
        //朴素二进制优化（多重背包）
        public int mixedMaxValue(int N, int C, int[] s, int[] v, int[] w) {
            int[] f = new int[C + 1];
            List<Integer> vv = new ArrayList<>(), ww = new ArrayList<>();
            int ss = 0;
            //s,v,w扁平化
            for (int i = 0; i < N; i++) {
                ss += s[i];
                vv.add(v[i]);
                ww.add(w[i]);
            }
            //转为0-1背包问题
            for (int i = ss - 1; i >= 0; i--) {
                for (int j = C; j >= ww.get(i); j--) {
                    f[j] = Math.max(f[j], f[j - ww.get(i)] + vv.get(i));
                }
            }
            return f[C];
        }
    }

    public int mixedMaxValue1(int N, int C, int[] s, int[] v, int[] w) {
        int[] f = new int[C + 1];
        List<Integer> vv = new ArrayList<>(), ww = new ArrayList<>();
        int ss = 0;
        //二进制扁平化
        for (int i = 0; i < N; i++) {
            int cur = s[i];
            for (int j = 1; j < cur; j *= 2) {
                cur -= j;
                vv.add(j * v[i]);
                ww.add(j * w[i]);
            }
            if (cur != 0) {
                vv.add(cur * v[i]);
                ww.add(cur * w[i]);
            }
        }

        ss = vv.size();

         //转为0-1背包问题
         for (int i = ss - 1; i >= 0; i--) {
            for (int j = C; j >= ww.get(i); j--) {
                f[j] = Math.max(f[j], f[j - ww.get(i)] + vv.get(i));
            }
        }

        return f[C];

    }

     //s: s[i] == 0, 只能取一次；s[i] < 0, 取无限次； s[i] > 0, 最多取s[i]次
     public int mixedMaxValue2(int N, int C, int[] s, int[] v, int[] w) {
        int[] f = new int[C + 1];
        List<Integer> vv = new ArrayList<>(), ww = new ArrayList<>();
        int ss = 0;

        for (int i = 0; i < N; i++) {
            int cur = s[i];
            if (cur == 0) {
                vv.add(v[i]);
                ww.add(w[i]);
            } else if (cur < 0) {
                //TODO: 标记无限背包问题
                ww.add(-w[i]);
                vv.add(v[i]);
            } else {
                for (int k = 1; k <= cur; k++) {
                    cur -= k;
                    vv.add(k * v[i]);
                    ww.add(k * w[i]);
                }
                if (cur > 0) {
                    vv.add(cur * v[i]);
                    ww.add(cur * w[i]);
                }
            }
        }

        ss = ww.size();

        for (int i = ss - 1; i >= 0; i--) {
            int cur = ww.get(i);

            if (cur > 0) {
                //0-1背包, 需要从大到小遍历
                for (int j = C; j >= cur; j--) {
                    f[j] = Math.max(f[j], f[j - cur] + vv.get(i));
                }
            } else {
                //无穷背包，需要从小到大遍历，利用本轮的最优解
                cur = -cur;
                for (int j = cur; j <= C; j++) {
                    f[j] = Math.max(f[j], f[j - cur] + vv.get(i));
                }
            }
            
        }


        return f[C];
    }

}
